package Algorithm.dynamicProgramming.knapsackDp;

/**
 * 完全背包基础问题：
 * 有n种物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每种物品有无限件，求解能装入背包里物品最大价值总和。
 * 参考：https://mp.weixin.qq.com/s/nke1OjkhKACaONx1opk8AA
 */
public class CompleteKnapsackBasic {

    /**
     * 1. 定义dp：dp[i][j]为背包容量为j时从前i件物品中选取能获得的最大价值
     * 2. 状态转移方程：对于dp[i][j]可分为以下两种情况，
     *              （1）当不选第i件物品时，dp[i][j]即为容量j从前i-1件物品中选取能获得的最大价值dp[i-1][j]
     *              （2）当选k个第i件物品时，dp[i][j] = k*value[i-1] + dp[i-1][j-k*weight[i-1]]
     *              故dp[i][j] = max(k*value[i-1]+dp[i-1][j-k*weight[i-1]]), 故dp[i][j-weight[i-1]] = max(k1*value[i-1]+dp[i-1][j-(k1+1)*weight[i-1]]),k1属于[0, k-1]
     *              因此dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i-1]] + value[i-1])
     *              简单来说，就等于选一个第i件物品，然后剩余重量在前i件物品中任意选的最大价值
     * 3. 初始化：dp[0][j]=0;dp[i][0]=0
     * 4. 递推：从上到下逐层遍历
     */
    public int completeKnapsackBasic(int[] weight, int[] value, int w) {
        int[][] dp = new int[weight.length+1][w+1];
        for (int i = 1;i <= weight.length;i++) {
            for (int j = 1;j <= w;j++) {
                if (weight[i-1] > j) //必须判断第i件物品重量是否直接超过了j
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-weight[i-1]] + value[i-1]);
            }
        }
        return dp[weight.length][w];
    }

    /**
     * 优化：滚动数组。通过分析发现，每一层中的dp[i][j]只和左边的数据及正上方的dp[i-1][j]有关，故可只用一个一维数组dp[j]来表示上一层的数据，
     *      在遍历当前层时正序遍历滚动刷新dp[j]
     * 1. 定义dp：dp[j]为一层中背包容量为j时能获得的最大价值
     * 2. 状态转移公式：在当前层中d[j] = max(d[j], dp[j-weight[i]]+value[i]) 括号中的d[j]为上一层的数据，d[j-weight[i]]为当前层数据
     * 3. 初始化：初始在第0层，dp[]全为0
     * 4. 递推：从上到下逐层遍历 每一层中采用正序遍历
     */
    public int completeKnapsackBasic2(int[] weight, int[] value, int w) {
        int[] dp = new int[w+1];
        for (int i = 0;i < weight.length;i++) {
            for (int j = 1;j <= w;j--) {
                if (j >= weight[i]) //j小于weight时直接继承上一层的数据
                    dp[j] = Math.max(dp[j], dp[j-weight[i]+value[i]]);
            }
        }
        return dp[w];
    }
}
